package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/3/20 10:51 AM
 */
public class 查找当前位置向前向后的第一个最小值 {


    public void findPreNextMin(int[] nums) {


        if (nums == null || nums.length == 0) {

            return;
        }

        // 构造一个单调递增栈
        Stack<Integer> stack = new Stack<>();

        int[] leftMinIndexs = new int[nums.length];
        int[] rightMinIndexs = new int[nums.length];

        for (int i = 0; i <nums.length; i++) {

            leftMinIndexs[i] = rightMinIndexs[i] = -1;
        }

        // 3,2,5,7,1,0,6
        for (int i = 0; i < nums.length; i++) {

            if (stack.isEmpty()) {

                stack.push(i);
                continue;
            }

            if (nums[stack.peek()] <= nums[i]) {

                leftMinIndexs[i] = stack.peek();
                stack.push(i);
            }else {

                while (!stack.isEmpty() &&  nums[stack.peek()] >= nums[i]) {

                    rightMinIndexs[stack.pop()] = i;
                }

                if (!stack.isEmpty()) {

                    leftMinIndexs[i] = stack.peek();
                }
                stack.push(i);
            }
        }

        System.out.println(Arrays.toString(leftMinIndexs));
        System.out.println(Arrays.toString(rightMinIndexs));


    }
}
